146. LRU Cache
Medium

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:
Could you do get and put in O(1) time complexity?

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

 

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 3000
  • 0 <= value <= 104
  • At most 3 * 104 calls will be made to get and put.
Accepted
776.5K
Submissions
2.1M
Seen this question in a real interview before?
Related Topics

Average Rating: 3.87 (211 votes)

Premium

Solution


Approach 1: Ordered dictionary

Intuition

We're asked to implement the structure which provides the following operations in O(1)\mathcal{O}(1) time :

  • Get the key / Check if the key exists

  • Put the key

  • Delete the first added key

The first two operations in O(1)\mathcal{O}(1) time are provided by the standard hashmap, and the last one - by linked list.

There is a structure called ordered dictionary, it combines behind both hashmap and linked list. In Python this structure is called OrderedDict and in Java LinkedHashMap.

Let's use this structure here.

Implementation

Complexity Analysis

  • Time complexity : O(1)\mathcal{O}(1) both for put and get since all operations with ordered dictionary : get/in/set/move_to_end/popitem (get/containsKey/put/remove) are done in a constant time.

  • Space complexity : O(capacity)\mathcal{O}(capacity) since the space is used only for an ordered dictionary with at most capacity + 1 elements.


Approach 2: Hashmap + DoubleLinkedList

Intuition

This Java solution is an extended version of the the article published on the Discuss forum.

The problem can be solved with a hashmap that keeps track of the keys and its values in the double linked list. That results in O(1)\mathcal{O}(1) time for put and get operations and allows to remove the first added node in O(1)\mathcal{O}(1) time as well.

compute

One advantage of double linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail.

One particularity about the double linked list implemented here is that there are pseudo head and pseudo tail to mark the boundary, so that we don't need to check the null node during the update.

compute

Implementation

Complexity Analysis

  • Time complexity : O(1)\mathcal{O}(1) both for put and get.

  • Space complexity : O(capacity)\mathcal{O}(capacity) since the space is used only for a hashmap and double linked list with at most capacity + 1 elements.

Report Article Issue

Comments: 92
calvinchankf's avatar
Read More

how come this question is downgraded as a medium question suddenly?

67
Show 6 replies
Reply
Share
Report
Kalguksu's avatar
Read More

Using an OrderedDict / LinkedHashMap to solve this problem in an interview setting is like using [::-1] / .reverse() to solve how to reverse a string, yeah you got it right but is that what the interviewer is looking for?

620
Show 28 replies
Reply
Share
Report
granola's avatar
Read More

I'd find a much better explanation and solution from the discussion section.

105
Hide 5 replies
Reply
Share
Report
tytakoff's avatar
Read More

leetcode solution and discussions complement each other

1
Reply
Share
Report
gchggy's avatar
Read More

it would be nice if you posted a link to whatever you found better in the discuss section.

13
Reply
Share
Report
abrahamab's avatar
Read More

True, but in this case, someone copy pasted the same solution in discussion.

2
Reply
Share
Report
phani3's avatar
Read More

It's always true somehow

3
Reply
Share
Report
alexworden's avatar
Read More

I really like the dummy head & tail technique. Much more simple implementation with those in place and really minimal extra memory overhead. I just spent an hour catching all the edge cases without them! I'm puzzled why my solution is slower than most - I presume most solutions are cheating and using an LinkedHashMap. I also suspect the performance numbers are based on unrealistically small sample sets.

46
Show 1 reply
Reply
Share
Report
softwareshortcut's avatar
Read More

Java Solution. Not a huge fan of the code proposed for solution #2. Here is a more straight forward code (same approach, just cleaner code).

class Node {
  int value;
  int key;
  Node prev;
  Node next;
  public Node() {}

  public Node(int key, int value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  Node head;
  Node tail;
  
  public DoublyLinkedList() {
    head = new Node();
    tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = head;
  }
  
  public void insertHead(Node n) {
    n.prev = head;
    n.next = head.next;
    head.next.prev = n;
    head.next = n;    
  }
  
  public void remove(Node n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
  }
  
  public int removeTail() {
    Node n = tail.prev;
    int key = n.key;
    remove(n);
    
    return key;
  }
}

class LRUCache {
  Map<Integer,Node> cache;
  DoublyLinkedList list;
  int capacity;
  
  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.cache = new HashMap<>();
    this.list = new DoublyLinkedList();
  }
  
  public int get(int key) {
    if (!cache.containsKey(key)) 
        return -1;    
    update(key, cache.get(key));
      
    return cache.get(key).value;
  }
  
  public void put(int key, int value) {
    Node n = new Node(key, value);
      
    if (cache.containsKey(key))
      list.remove(cache.get(key));
    else if (cache.size() >= capacity) {
        int k = list.removeTail();
        cache.remove(k);
    }
        
    list.insertHead(n);
    cache.put(key, n);
  }
  
  private void update(int key, Node n) {    
    list.remove(n);
    list.insertHead(n);
    cache.put(key, n);
  }
}

48
Show 6 replies
Reply
Share
Report
liaison's avatar
Read More

@KingXun good question! The key in DLinkedNode would help us to remove the node itself from the cache at the moment the node becomes stale and is removed along with the invocation of the function popTail. We need to keep the key along with the node itself, because when the node is removed, we are not blessed with the key from the caller of LRU cache.

11
Reply
Share
Report
ltbtb_rise's avatar
Read More

tried everything I could, stack, de-que, priority queue, etc. I just never thought about using the f..king linked list! This drives me crazy.

9
Hide 3 replies
Reply
Share
Report
piepi's avatar
Read More

@wolfhound115 Can't delete a random node in deque except for the first or last. DLL can. That's why a vanilla Linked List won't work as well.

0
Reply
Share
Report
wolfhound115's avatar
Read More

wait but a deque is effectively a doubly linked list right? (at least in the python implementation of it)

-1
Reply
Share
Report
hello_Worldxxx's avatar
Read More

It's crazy. Agree.

0
Reply
Share
Report
yang-zhang-syd's avatar
Read More

why remove oldest? what if a cache is frequently used and the eldest the same time?

22
Show 5 replies
Reply
Share
Report
yh32's avatar
Read More

Does the interviewer really expects you to write this much code in just 30 mins?

10
Show 6 replies
Reply
Share
Report
doctorjuice's avatar
Read More

I do not understand how this could possibly be implemented within 30 minutes without having prior knowledge of the question, especially if it is a whiteboard interview.

Can we assume a doubly linked list implementation is provided, implement only get and put, using assumed functions for doubly linked list? That would seem reasonable, otherwise the volume of this code just seems too much, even more so if you have to handle edge cases because you didn’t use dummy head and tail variables.

5
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/02/2021 19:20Accepted292 ms42.7 MBcpp
05/30/2021 12:22Accepted96 ms42.6 MBcpp
04/26/2021 11:58Accepted100 ms42.7 MBcpp
04/26/2021 11:58Accepted96 ms42.7 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium